package com.backpack;

import java.util.ArrayList;

/**
 * 输入：n = 12
 * 输出：3
 * 解释：12 = 4 + 4 + 4
 * 和为完全平方数的最少数量
 */
public class PerfectSquares0113_279 {
    public int numSquares(int n) {
        if(n == 1) return 1;
        //完全背包问题
        //dp[i] 表示 容量和为 i 的背包中  至少能够放 dp[i]个完全平方数       返回值求dp[n]
        int[] dp = new int[n+1];

        //物品 需要计算 <=n 的所有完全平方数
        ArrayList<Integer> nums = new ArrayList<>();
        for (int i = 1; i <= n / 2; i++) {
            if(i*i <= n) nums.add(i*i);
        }

        //初始化,非 0 下标元素初始为最大值
        dp[0] = 0;
        for (int i = 1; i < dp.length; i++) {
            dp[i] = Integer.MAX_VALUE;
        }

        //递推公式： dp[j] = Math.min(dp[j],dp[j-nums.get(i)] + 1);
        //遍历顺序：先遍历物品（正序），再遍历背包（正序，因为可以重复使用同一元素）     颠倒可行
        for (int i = 0; i < nums.size(); i++) {
            for (int j = nums.get(i); j < dp.length; j++) {
                if(dp[j-nums.get(i)] != Integer.MAX_VALUE){
                    dp[j] = Math.min(dp[j],dp[j-nums.get(i)] + 1);
                }
            }
        }
        return dp[n];
    }
}
